package ar.edu.itba.it.npuzzle
import scala.Math.abs
import scala.collection.immutable.HashSet
import scala.collection.immutable.TreeSet
import scala.util.control.Breaks.break
import scala.util.control.Breaks.breakable
import scala.util.Random
import State._

sealed abstract class Direction(val value: Int)
case object Up extends Direction(-3)
case object Left extends Direction(-1)
case object Right extends Direction(1)
case object Down extends Direction(3)

object State {
  val empty = '9'
  val goal = Vector('1', '2', '3', '4', '5', '6', '7', '8', empty)
  val moves = Array(
    List(Right, Down), List(Left, Right, Down), List(Left, Down),
    List(Up, Right, Down), List(Up, Left, Right, Down), List(Up, Left, Down),
    List(Up, Right), List(Up, Left, Right), List(Up, Left))
  def apply(data: Vector[Vector[Char]]): State = new State(0, data.flatten)

  def shift(data: Vector[Char], pos: Int, dir: Direction): Vector[Char] = {
    val value = data(pos); data.updated(pos, data(pos + dir.value)).updated(pos + dir.value, value)
  }

  implicit object StateOrdering extends Ordering[State] {
    def compare(x: State, y: State): Int = {
      var result = x.f - y.f
      if (result == 0) {
        breakable {
          for ((x, y) <- x.data.zip(y.data)) {
            result = x - y
            if (result != 0) break
          }
        }
      }
      result
    }
  }
}

class State(val g: Int, val data: Vector[Char], ss: List[Direction] = Nil) {
  def neighbors: List[State] = moves(emptySlot).map(d => new State(g + 1, shift(data, emptySlot, d), d :: ss))

  lazy val f = g + h
  def isGoal = data == State.goal
  def steps = ss.reverse
  override def toString = "Data: " + data + " - h: " + f
  private val emptySlot = data.findIndexOf(_ == empty)
  private lazy val h = (for (row <- 0 to 2; column <- 0 to 2; value = data(row * 3 + column)) yield (distance(row, column, value))).sum
  private def distance(row: Int, column: Int, value: Char) = abs(row - (value - '1') / 3) + abs(column - (value - '1') % 3)

  def canEqual(other: Any) = other.isInstanceOf[State]
  override val hashCode = 41 * data.hashCode
  override def equals(other: Any) = other match {
    case s: State => canEqual(s) && data == s.data
    case _ => false
  }
}

object Solver extends App {
  implicit def intWithTimes(n: Int) = new {
    def times(f: => Unit) = 1 to n foreach { _ => f }
  }

  def randomBoard = {
    var data = goal
    100 times {
      val pos = data.findIndexOf(_ == empty)
      val validMoves = moves(pos)
      data = shift(data, pos, validMoves(Random.nextInt(validMoves.size)))
    }
    val iter = data.grouped(3)
    Vector(iter.next, iter.next, iter.next)
  }

  val board = randomBoard
  println(board)
  new Solver(board).solve
}

class Solver(data: Vector[Vector[Char]]) {
  var expanded = new HashSet[State]
  var toExpand = new TreeSet[State]

  def solve {
    var solution: Option[List[Direction]] = None
    toExpand += State(data)
    breakable {
      while (!toExpand.isEmpty) {
        val state = toExpand.first
        toExpand -= state
        if (!expanded.contains(state)) {
          expanded += state
          if (state.isGoal) { solution = Some(state.steps.reverse); break }
          toExpand ++= state.neighbors
        }
      }
    }

    println(solution.getOrElse("No solution found"))
  }
}